package leetcode.code1498;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	static long mod = (int) 1e9 + 7;
	static Long[] dp;

	static {
		int m = (int) 1e5;
		dp = new Long[m + 1];
		dp[0] = 1l;
		dp[1] = 2l;
		for (int i = 2; i <= m; i++) {
			dp[i] = dp[i - 1] * 2 % mod;
		}
	}

	public int numSubseq(int[] nums, int target) {
		Arrays.sort(nums);
		int l = 0, r = nums.length - 1;
		int t = -1;
		while (l <= r) {
			int mid = ((r - l) >> 1) + l;
			int cur = nums[mid];
			if (cur <= target) {
				t = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		if (t == -1) {
			return 0;
		}
		l = -1;
		r = t;
		long ans = 0;
		while (l < r) {
			while (l <= r && l + 1 < nums.length && nums[l + 1] + nums[r] <= target) {
				l++;
			}
			if (l < r) {
				ans += (dp[l+1] - 1) * dp[r - l - 1] % mod;
				r--;
			}
		}
		if (r >= 0) {
			ans += dp[r + 1] - 1;
			ans %= mod;
		}
		return (int) (ans % mod);
	}

	public long pow(int x) {
		if (dp[x] != null) {
			return dp[x];
		}
		long ans = pow(x >> 1) % mod;
		ans = (ans * ans) % mod;
		ans = (x & 1) == 1 ? ans * 2 % mod : ans;
		dp[x] = ans;
		return ans;
	}

	@Override
	public void debug4() {

		H.compare(91931447, this.numSubseq(H.str2array3(
				"[9,25,9,28,24,12,17,8,28,7,21,25,10,2,16,19,12,13,15,28,14,12,24,9,6,7,2,15,19,13,30,30,23,19,11,3,17,2,14,20,22,30,12,1,11,2,2,20,20,27,15,9,10,4,12,30,13,5,2,11,29,5,3,13,22,5,16,19,7,19,11,16,11,25,29,21,29,3,2,9,20,15,9]"),
				32));
		H.compare(127, this.numSubseq(H.str2array3("[5,2,4,1,7,6,8]"), 16));
		H.compare(4, this.numSubseq(H.str2array3("[2,13,16,13]"), 17));
		H.compare(60, this.numSubseq(H.str2array3("[2,2,3,4,13,16,13]"), 17));
		H.compare(755695356,
				this.numSubseq(H.str2array3(
						"[2,3,3,4,16,7,3,3,4,6,7,13,3,4,16,7,3,3,4,6,7,13,3,4,6,7,13,3,4,6,7,3,3,4,6,7,3,3,4,6,7]"),
						17));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		int mod = (int) 1e9 + 7;
//		long a = (long) Math.pow(2, 36);
//		System.out.println(a % mod);
//		System.out.println(so.pow(36));
//		System.out.println(1106473174l % mod);
	}

}
